#include<stdio.h>
#include<stdlib.h>
#include"homework.h"
#define MAX 10
#define Elementype int 
struct Array
{
    Elementype a[MAX];
    int len;
};

void Travel(Elementype *a,int len)
{
    for(int i=0;i<len;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");

}

void ReTravel(Elementype *a,int len)
{
    for(int i=len-1;i>=0;i--)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

void InsertTail(struct Array *array,Elementype element)
{
    if(array->len>=MAX)
    {
        printf("out of range!\n");
        return;
    }
    array->a[array->len]=element;
    array->len++;
}

void InsertHead(struct Array *array,Elementype element)
{
    if(array->len>=MAX)
    {
        printf("out of range!\n");
        return;
    }   
    
    for(int i=array->len;i>0;i--)
    {
        array->a[i]=array->a[i-1];
    }
    array->a[0]=element;
    array->len++;
}

void InsertIndex(struct Array *array,Elementype element,int index)
{
    if(array->len>=MAX)
    {
        printf("out of range!\n");
        return;
    }   

    if(index<0 || index>array->len)
    {
        printf("invalid place!\n");
        return;      
    }

    for(int i=array->len;i>index;i--)
    {
        array->a[i]=array->a[i-1];
    }

    array->a[index]=element;
    array->len++;
}

void RemoveIndex(struct Array *array,int index)
{
    if(index<0 || index>=array->len)
    {
        printf("invalid place!\n");
        return;      
    }

    for(int i=index+1;i<array->len;i++)
    {
        array->a[i-1]=array->a[i];
    }
    array->len--;
}

void RemoveElement(struct Array *array,Elementype element)
{
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==element)
        {
            RemoveIndex(array,i);
        }
    }
}

Elementype FindByIndex(struct Array *array,int index)
{
    if(index<0 || index>=array->len)
    {
        printf("invalid place!\n");
        return 0;      
    }    

    return array->a[index];
}

int* FindByElement(struct Array*array,Elementype element)
{
    int* findVector=(int *)malloc((array->len+1)*sizeof(Elementype));
    int count=0;
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==element)
        {
            count++;
            findVector[count]=i;
        }
    }
    findVector[0]=count;
    return findVector;
}

int* FindByElement2(struct Array*array,Elementype element)
{
    int* findVector=(int *)malloc((array->len+1)*sizeof(Elementype));
    int count=0;
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==element)
        {
            findVector[count]=i;
            count++;
        }
    }
    findVector[count]=-1;
    return findVector;
}

void SetValueByIndex(struct Array *array,int index,Elementype element)
{
    if(index<0 || index>=array->len)
    {
        printf("invalid place!\n");
        return;      
    }   
    array->a[index]=element;
}

void SetValueByElement(struct Array *array,Elementype old_value,Elementype new_value)
{
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==old_value)
        {
            array->a[i]=new_value;
        }
    }
}

struct Array* FindIntersection(struct Array *array1,struct Array *array2)
{
    struct Array *intersection=(struct Array *)malloc(sizeof(struct Array));
    if(intersection==NULL)
        return NULL;
    for(int i=0;i<array1->len;i++)
    {
        for(int j=0;j<array2->len;j++)
        {
            if(array1->a[i]==array2->a[j])
            {
                int flag=0;
                for(int k=0;k<intersection->len;k++)
                {
                    if(intersection->a[k]==array1->a[i])
                    {
                        flag=1;
                    }
                }
                if(flag==0)
                {
                    InsertTail(intersection,array1->a[i]);
                }

            }
        }

    }
    return intersection;
}

void Deduplication(struct Array *array)
{
    fastSort(array->a,0,array->len-1);
    for(int i=0;i<array->len-1;i++)
    {
        if(array->a[i+1]==array->a[i])
        {
            RemoveIndex(array,i+1);
            i--;
        }
    }
}

struct Array* FindUnionSet(struct Array *array1,struct Array *array2)
{
    struct Array *unionset=(struct Array *)malloc(sizeof(struct Array));
    if(unionset==NULL)
        return NULL;
    for(int i=0;i<array1->len;i++)
    {
        InsertTail(unionset,array1->a[i]);
    }
    for(int i=0;i<array2->len;i++)
    {
        InsertTail(unionset,array2->a[i]);
    }
    Deduplication(unionset);
    return unionset;
}

struct Array* MergeArray(struct Array *array1,struct Array *array2)
{
    fastSort(array1->a,0,array1->len-1);
    fastSort(array2->a,0,array2->len-1);
    struct Array *Merge=(struct Array *)malloc(sizeof(struct Array));
    Merge->len=0;
    if(Merge==NULL)
        return NULL;   
    int i=0,j=0;
    while(i<array1->len && j<array2->len)
    {
        if(array1->a[i]<=array2->a[j])
        {
            InsertTail(Merge,array1->a[i]);
            i++;
        }
        else
        {
            InsertTail(Merge,array2->a[j]);
            j++;
        }
    }
    while(i<array1->len)
    {
        InsertTail(Merge,array1->a[i]);
        i++;
    }
    while(j<array2->len)
    {
        InsertTail(Merge,array2->a[j]);
        j++;
    }
    return Merge;
}


int main()
{
    struct Array array;
    struct Array array1;
    array.len=0;
    array1.len=0;

    // for(int i=0;i<5;i++)
    // {
    //     InsertTail(&array,i+1);
    //     InsertHead(&array,i+1);
    //     InsertIndex(&array,i+1,2);
    // }

    // Travel(array.a,array.len);

    // InsertIndex(&array,100,2);
    // Travel(array.a,array.len);

    // RemoveIndex(&array,2);
    // Travel(array.a,array.len);
    // printf("%d\n",FindByIndex(&array,2));

    InsertTail(&array,5);
    InsertTail(&array,3);
    InsertTail(&array,1);
    // InsertTail(&array,3);



    InsertTail(&array1,6);
    InsertTail(&array1,4);
    InsertTail(&array1,2);
    InsertTail(&array1,9);
    // InsertTail(&array1,4);
    // InsertTail(&array1,5);


    // int *findVector=FindByElement(&array,2);
    // for(int i=0;i<=findVector[0];i++)
    // {
    //     printf("%d ",findVector[i]);
    // }
    // printf("\n");

    // int *findVector=FindByElement2(&array,2);
    // int *temp=findVector;
    // while(*temp!=-1)
    // {
    //     printf("%d ",*temp);
    //     temp++;
    // }
    // printf("\n");
    // free(findVector);

    // SetValueByElement(&array,2,20);
    // Travel(array.a,array.len);

    // struct Array *a=FindIntersection(&array,&array1);
    // struct Array *a=FindUnionSet(&array,&array1);
    struct Array *a=MergeArray(&array,&array1);
    // Deduplication(&array);
    // Travel(array.a,array.len);
    Travel(a->a,a->len);
    return 0;
}